package com.google.code.numbertheory;

/**
 * Greatest common divisor (gcd) of two non-zero integers,
 * is the largest positive integer that divides both numbers without remainder.
 */
public class GreatestCommonDivisor {
    /**
     * Euclidean Algorithm
     * @return greatest common divisor of two integers
     */
    public static int gcd(int a, int b) {
        while(a!= 0 && b!= 0) {
            if(a >= b) {
                a = a % b;
            } else {
                b = b % a;
            }
        }
        // either a or b is 0
        return a + b;
    }

    public static int gcd(int ... nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int gcd = gcd(nums[0], nums[1]);
        for(int i=2;i<nums.length;i++) {
            gcd = gcd(gcd, nums[i]);
        }
        return gcd;
    }
}
